#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <MyString.h>
#define ElementType void*

typedef struct
{
    int id;
    MyStr name;
    int age;
}Stu;
Stu * CreateStu(const int id,const char *name,const int age)
{
    Stu *s = (Stu*)malloc(sizeof(Stu));
    if(s == NULL)
    {
        return NULL;
    }
    s->id = id;
    s->age = age;
    s->name = GetString(name);
    return s;
}
bool SortByAge(void *ptr1,void *ptr2)
{
    Stu *s1 = (Stu *)ptr1;
    Stu *s2 = (Stu *)ptr2;
    if(s1->age < s2->age)
        return true;
    return false;
}
void ClearStu(void *ptr)
{
    Stu *s = (Stu*)ptr;
    //printf("释放学生对象%s\n",s->name.string);
    ClearString(&s->name);
    free(s);
}
void PrintStu(void *ptr)
{
    Stu *s = (Stu *)ptr;
    printf("学生学号：%d 学生姓名：%s 学生年龄：%d\n",s->id,s->name.string,s->age);
}

//节点
struct Node
{
    //数据域
    ElementType data;
    //指针域
    struct Node * next;
};

//链表结构体
typedef struct LinkList
{
    //头节点指针
    struct Node * head;
    int len;//链表的长度
}Llist;

//创建节点的接口
struct Node * CreateNode(ElementType element)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL)
    {
        printf("create Node malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    return newNode;
}

void InitLlist(Llist *l)
{
    //设置头节点
    l->head = CreateNode(0);
    l->len = 0;
}

// //链表尾插法
// void InsertListTail(Llist *l,ElementType element)
// {
//     //遍历指针
       //不直接令TravelPoint为head->next是为了初始化链表后可以插入，否则前一个节点将丢失
//     struct Node *TravelPoint = l->head;
//     //这个节点是尾巴
//     while(TravelPoint->next != NULL)
//     {
//         TravelPoint = TravelPoint->next;
//     }
//     TravelPoint->next = CreateNode(element);
//     l->len++;
// }

// //头插法
// void InsertListHead(Llist *l,ElementType element)
// {
//     struct Node *newNode = CreateNode(element);
//     newNode->next = l->head->next;
//     l->head->next = newNode;
//     l->len++;
// }

// //中间插
// void InsertByIndex(Llist *l,ElementType element,int index)
// {
//     if(index < 0 || index > l->len)
//     {
//         printf("插入了非法的位置：%d len ： %d\n",index,l->len);
//         return;
//     }

//     struct Node *TravelPoint = l->head;
//     for(int i = 0; i < index; i++)
//     {
//         TravelPoint = TravelPoint->next;
//     }

//     struct Node *newNode = CreateNode(element);
//     newNode->next = TravelPoint->next;
//     TravelPoint->next = newNode;
//     l->len++;
// }

//按位置删除
void RemoveByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("删除的位置非法：%d len ： %d\n",index,l->len);
        return;
    }

    struct Node* TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }

    struct Node *freeNode = TravelPoint->next;
    TravelPoint->next = freeNode->next;
    free(freeNode);
    l->len--;
}

//按值删除
void  RemoveByElement(Llist * l,ElementType element)
{
    struct Node* TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //t的下一个节点需要删除
        if(TravelPoint->next->data == element)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            struct Node *freeNode = TravelPoint->next;
            TravelPoint->next = freeNode->next;
            free(freeNode);
            l->len--;
        }
        else
        {
            TravelPoint = TravelPoint->next;
        }
    }
}

//按位修改
void UpdateByIndex(Llist *l,int index,ElementType newValue)
{
    if(index < 0 || index >= l->len)
    {
        printf("更改的位置非法：%d len ： %d\n",index,l->len);
        return;
    }
    struct Node* TravelPoint = l->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->data = newValue;
}

//按值修改
void  UpdateByElement(Llist * l,ElementType oldValue,ElementType newValue)
{
    struct Node* TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //t的下一个节点需要删除
        if(TravelPoint->next->data == oldValue)
        {
            TravelPoint->next->data = newValue;
        }
        TravelPoint = TravelPoint->next;
    }
}

// void Travel(Llist *l)
// {
//     printf("len: %d\n",l->len);
//     printf("\n================================================================\n");
//     //头节点不参与遍历操作
//     struct Node *TravelPoint = l->head->next;
//     while(TravelPoint != NULL)
//     {
//         printf("%d ",TravelPoint->data);
//         //走向下一个节点
//         TravelPoint = TravelPoint->next;
//     }
//     printf("\n================================================================\n");
// }

void Travel(Llist *l,void (*funcptr)(void*))
{
    printf("len: %d\n",l->len);
    printf("\n================================================================\n");
    //头节点不参与遍历操作
    struct Node *TravelPoint = l->head->next;
    while(TravelPoint != NULL)
    {
        funcptr(TravelPoint->data);
        //走向下一个节点
        TravelPoint = TravelPoint->next;
    }
    printf("\n================================================================\n");
}


//按位置查
ElementType* FindByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("查找的位置非法：%d len ： %d\n",index,l->len);
        return NULL;
    }
    struct Node *TravelPoint = l->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->data;
}

//按值查找
//指向指针数组的数组指针
struct Node** FindByElement(Llist *l,ElementType element)
{
    //len个指针的空间+1，多一个位置放结束符
    struct Node** dyA = (struct Node**)malloc(sizeof(struct Node*) *(l->len+1));
    if(dyA == NULL)
    {
        return NULL;
    }
    int count = 0;
    struct Node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //t的下一个节点需要删除
        if(TravelPoint->next->data == element)
        {
            //把符合条件的节点指针放入数组中
            dyA[count] = TravelPoint->next;
            count++;
        }
        TravelPoint = TravelPoint->next;
    }
    //最后一位放上NULL空地址，表征找寻结束符号
    dyA[count] = NULL;
    return dyA;
}

void Swap(ElementType* value1,ElementType* value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

void FastSort(struct Node *start,struct Node *end, bool (*funcptr)(void *,void *))
//void FastSort(struct Node *start,struct Node *end)
{
    if(start == end)
    {
        return;
    }
    //p1指向链表排序数据的开头
    struct Node *p1 = start;
    //p2指向p1后
    struct Node *p2 = start->next;

    //判断循环结束条件
    while(p2 != end)
    {
        //当p2的值比基准值小
        if(funcptr(p2->data ,start->data) == true)
        //if(p2->data < start->data)
        {
            //p1指针后移
            p1 = p1->next;
            //将比基准值小的数前移
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    //将基准值和p1值互换，使p1指向的值处于中间位置，即在它左边的值均比它小，在它右边的值均比它大
    Swap(&start->data,&p1->data);
    //经过一轮转换后，p1为左侧小序列的末尾，p2为右侧大序列的末尾
    FastSort(start,p1,funcptr);
    FastSort(p1->next,end,funcptr);
}

//单链表的逆序：递归和非递归
void Reserve(Llist *l)
{
    if(l->len == 0 || l->len == 1)
        return;
    //让所有逆序都能成立，尤其是尾巴的next为NULL
    struct Node *prev = NULL;
    struct Node *cur = l->head->next;
    struct Node *Next = cur->next;

    while(Next != NULL)
    {
        //将c当前的指向往前指
        cur->next = prev;
        //三个指针都向后走
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;
    l->head->next = cur;
}

//递归逆序
struct Node* Reserve2(struct Node *node)
{
    //递归的终止条件
    if(node->next == NULL)
    {
        return node;
    }
    else
    {
        //层层接住这个尾巴(最后一个节点的地址)
        struct Node *tail = Reserve2(node->next);
        node->next->next = node;
        node->next = NULL;
        return tail;
    }
}

//归并
// Llist Merge(Llist *l1,Llist *l2)
// {
//     Llist list;
//     InitLlist(&list);
//     struct Node* p1 = l1->head->next;
//     struct Node* p2 = l2->head->next;
//     while(p1 != NULL && p2 != NULL)
//     {
//         if(p1->data > p2->data)
//         {
//             InsertListTail(&list,p2->data);
//             p2 = p2->next;
//         }
//         else
//         {
//             InsertListTail(&list,p1->data);
//             p1 = p1->next;
//         }
//     }

//     while(p1 != NULL)
//     {
//         InsertListTail(&list,p1->data);
//         p1 = p1->next;
//     }

//     while(p2 != NULL)
//     {
//         InsertListTail(&list,p2->data);
//         p2 = p2->next;
//     }
//     return list;
    
// }

void FreeLlist(Llist *l)
{
    while(l->head != NULL)
    {
        struct Node *next = l->head->next;
        free((l->head));
        l->head = next;
    }
    l->len = 0;
}

int main()
{
    // srand(time(NULL));
    // Llist l;
    // InitLlist(&l);

    // for(int i = 1; i <= 10; i++)
    // {
    //     InsertListTail(&l,i);
    // }

    // InsertListHead(&l,1);
    // Travel(&l);
    // //InsertByIndex(&l,99,0);
    // //RemoveByIndex(&l,1);
    // //RemoveByElement(&l,1);
    // // Travel(&l);
    // // UpdateByIndex(&l,0,100);
    // UpdateByElement(&l,1,100);
    // Travel(&l);

    // // int* ptr = FindByIndex(&l,2);
    // // if(ptr == NULL)
    // // {
    // //     printf("没找到！\n");
    // // }
    // // else
    // // {
    // //     printf("找到了:%d\n",*ptr);
    // // }

    // struct Node **dyA = FindByElement(&l,100);
    // int count = 0;
    // while(dyA[count] != NULL)
    // {
    //     printf("node element: %d\n",dyA[count]->data);
    //     count++;
    // }
    // free(dyA);

    // FreeLlist(&l);
    // Travel(&l);



    // srand(time(NULL));
    // Llist l;
    // InitLlist(&l);

    // for(int i = 1; i <= 10; i++)
    // {
    //     InsertListTail(&l,rand()%100);
    // }
    // Travel(&l);
    // FastSort(l.head->next,NULL);
    // Travel(&l);
    // l.head->next = Reserve2(l.head->next);
    // Travel(&l);

    // srand(time(NULL));
    // Llist l2;
    // InitLlist(&l2);

    // for(int i = 1; i <= 10; i++)
    // {
    //     InsertListTail(&l2,rand()%100);
    // }
    // Travel(&l2);
    // FastSort(l2.head->next,NULL);
    // Travel(&l2);
    //  l2.head->next = Reserve2(l2.head->next);
    // Travel(&l2);

    // Llist list;
    // InitLlist(&list);
    // list = Merge(&l,&l2);

    // Travel(&list);
    // FreeLlist(&l);
    // FreeLlist(&l2);
    // FreeLlist(&list);


    // Llist list;
    // InitLlist(&list);

    // InsertListTail(&list,CreateStu(1,"zhangsan",20));
    // InsertListTail(&list,CreateStu(2,"zhang",22));
    // InsertListTail(&list,CreateStu(3,"san",19));
    // FastSort(list.head->next,NULL,SortByAge);
    // Travel(&list,PrintStu);
    //FreeLlist(&list);
    return 0;
}